package com.cskaoyan.day02.single;

import com.cskaoyan.day01.linkdemo.Node;

/**
 * 单链表实现线性表
 * @author stone
 * @date 2022/01/28 09:51
 */
public class MyLinkedList {

    //维护链表
    private Node head;
    //链表的长度
    private int size;
    //增加方法，这些方法是操作链表的

    public boolean isEmpty() {
        //ctrl + alt + L → 不太建议使用这个快捷键
        //定位问题不方便 → 合作开发 → 版本控制工具git
        //ctrl + shift + enter
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * 向链表中增加结点
     * @param value
     * @return
     */
    public boolean add(String value) {
        //size==0
        if (isEmpty()) {
            //头结点指向新结点
            //Node newNode = new Node(value);
            //head = newNode;
            head = new Node(value);
            size++;
            return true;
        }
        //链表不为空
        //找到最后一个结点 → 遍历
        Node current = head;
        /*while (current != null) { // 会导致current最后指向的是null → 会导致空指针问题
            current = current.next;
        }*/
        while (current.next != null) {
            current = current.next;
        }
        //找到最后一个结点
        current.next = new Node(value);
        size++;
        return true;
    }

    public boolean remove(String value) {
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        //value和head.value是同一个值 → head.value.equal(value)
        //如果value=null → value == head.value或head.value==null
        //如果value！=null → value.equals(head.value)
        if (value == null) {
            //是否是头结点
            if (value == head.value) {//head.value==null
                //如果链表中只有一个结点了，这个结点就是head → 使用head=head.next 也是ok的
                head = head.next;
                size--;
                return true;
            } else {
                //要找到要移除结点的前一个结点
                //current是head的情况已经考虑了，现在current就是head.next
                //pre就应该从head开始
                Node pre = head;
                //Node current = pre.next;
                /*while (true) {
                    //退出条件 → 找到对应的值了 current.value == value 或current.value=null
                    //退出条件 → 遍历结束了没有找到对应的值 current == null
                    //退出条件之间的关系是：或
                    //遍历条件之间的关系是：且

                }*/
                //while (current != null && current.value != value) {
                while (pre.next != null && pre.next.value != value) {
                    pre = pre.next;
                    //current = current.next;//current = pre.next也行
                }
                //如果是没有找到对应值的情况
                //if (current == null) {
                if (pre.next == null) {
                    return false;
                }else {
                    pre.next = pre.next.next;
                    size--;
                    return true;
                }
            }
        } else {
            //value！=null的情况
            //判断是否是头结点
            if (value.equals(head.value)) {
                head = head.next;
                size--;
                return true;
            }else {
                Node pre = head;
                //Node current = pre.next;
                //只有值的比较和前面不一样
                //while (current != null && !value.equals(current.value)) {
                while (pre.next != null && !value.equals(pre.next.value)) {
                    pre = pre.next;
                    //current = current.next;//current = pre.next也行
                }
                //如果是没有找到对应值的情况
                //if (current == null) {
                if (pre.next == null) {
                    return false;
                }else {
                    pre.next = pre.next.next;
                    size--;
                    return true;
                }
            }
        }
    }

    public boolean contains(String value) {
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        if (value == null) {
            Node current = head;
            while (current != null && value != current.value) {
                current = current.next;
            }
            if (current == null) {
                return false;
            }
            return true;
        }else {
            Node current = head;
            while (current != null && !value.equals(current.value)) {
                current = current.next;
            }
            if (current == null) {
                return false;
            }
            return true;
        }
    }

    public boolean set(String origin, String value) {
        if (isEmpty()) {
            throw new RuntimeException("链表为空");
        }
        if (origin == null) {
            Node current = head;
            while (current != null && origin != current.value) {
                current = current.next;
            }
            if (current == null) {
                return false;
            }
            current.value = value;
            return true;
        }else {
            Node current = head;
            while (current != null && !origin.equals(current.value)) {
                current = current.next;
            }
            if (current == null) {
                return false;
            }
            current.value = value;
            return true;
        }
    }

    /**
     * index:链表的下标 从0开始 → size
     * 最后一个结点的下标为size-1
     * value:添加的新结点值域的值
     */
    public boolean add(int index, String value) {
        //参数合法性判断 index范围是啥 index=0~size
        //可以放到最后一个结点后面
        if (index < 0 || index > size) {
            throw new RuntimeException("参数不合法");
        }
        if (index == 0) {
            /*if (isEmpty()) {
                //head =null;
                //head = new Node(value,null);
                head = new Node(value, head);
            }else {
                head = new Node(value, head);
            }*/
            head = new Node(value, head);
            size++;
            return true;
        }
        //index=1~size
        Node pre = head;
        int tag = 1;
        //tag和index相等时找到目标位置,找到该位置的前一个结点
        while (tag++ != index) {
            pre = pre.next;
            //tag++;
        }
        //pre
        pre.next = new Node(value, pre.next);
        size++;
        return true;
    }

    /**
     * 根据下标删除对应的结点
     * @param index 下标 → index=0~size-1
     * @return
     */
    public String remove(int index) {
        if (index < 0 || index > size - 1) {//注意和根据index增加的范围有区别
            throw new RuntimeException("参数不合法");
        }
        //没有做链表为空判断 → 链表为空 size=0 → index<=-1 && index>=0
        String value = null;
        if (index == 0) {
            //value==head.value   value.equals(head.value)
            //头结点后移

            value = head.value;
            head = head.next;
        }else {
            //index=1~size-1
            //移除当前位置结点，我们通过谁来移除
            Node pre = head;
            int tag = 1;
            while (tag++ != index) {
                pre = pre.next;
            }
            //找到目标位置的前一个结点pre
            value = pre.next.value;
            pre.next = pre.next.next;
        }
        size--;
        return value;
    }

    //todo: 找当前结点
    public String get(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("参数不合法");
        }
        Node current = head;
        int tag = 0;
        while (tag++ != index) {
            current = current.next;
        }
        return current.value;
    }

    //todo: 找当前结点
    public boolean set(int index, String value) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("参数不合法");
        }
        Node current = head;
        int tag = 0;
        while (tag++ != index) {
            current = current.next;
        }
        current.value = value;
        return true;
    }

    //head头 rear屁股
    public void show() {
        if (isEmpty()) {
            System.out.println("链表为空");//抛出异常也行
            return;
        }
        //需要一个额外的标记 → 标记当前结点
        Node current = head;

        while (current != null) {
            System.out.print(current.value + "-->");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 建议实现数据结构时，结点写成内部类
     */
    class Node{
        String value;
        Node next;

        public Node(String value) {
            this.value = value;
        }

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
